<!doctype html>
<html>

<head>
    <title>quadtree-js Retrieve Nodes</title>
    <link rel="stylesheet" type="text/css" href="style.css?v=2" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />

		<!-- prism syntax highlighting (https://prismjs.com/) -->
		<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/themes/prism.min.css" integrity="sha512-tN7Ec6zAFaVSG3TpNAKtk4DOHNpSwKHxxrsiw4GHKESGPs5njn/0sMCUMl2svV4wo4BK/rCP7juYz+zx+l6oeQ==" crossorigin="anonymous" />
</head>

<body>

    <div class="outer">

        <h1><a href="https://github.com/timohausmann/quadtree-js">quadtree-js</a> <small>retrieve nodes</small></h1>

        <div id="canvasContainer">
            <canvas id="canvas" width="640" height="480"></canvas>
        </div>
			
        <p>
            <strong>Retrieve Nodes Example</strong>
        </p>
        <p>
            To retrieve that match your query and contain objects you can overwrite the retrieve function like below or use the <a href="https://github.com/timohausmann/quadtree-js/tree/retrieve-nodes">retrieve-nodes branch</a>.
        </p>
        <p>
            Github Issue: <a href="https://github.com/timohausmann/quadtree-js/issues/17">quadtree-js/issues/17</a>
        </p>

        <pre><code class="language-javascript">Quadtree.prototype.retrieve = function (pRect) {

    var indexes = this.getIndex(pRect),
        objects = this.objects;

    //modification: collect nodes
    var nodes = [];
    if (this.objects.length) nodes.push(this);


    //if we have subnodes, retrieve their objects
    if (this.nodes.length) {
        for (var i = 0; i < indexes.length; i++) {

            //modification: collect objects and nodes
            const retrieved = this.nodes[indexes[i]].retrieve(pRect);
            objects = objects.concat(retrieved.objects);
            nodes = nodes.concat(retrieved.nodes);
        }
    }

    //remove duplicate objects
    objects = objects.filter(function (item, index) {
        return objects.indexOf(item) >= index;
    });

    //modification: return objects and nodes
    return {
        objects: objects,
        nodes: nodes
    }
};</code></pre>

    </div>

    <!-- prism syntax highlighting -->
    <script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/prism.min.js" integrity="sha512-WkVkkoB31AoI9DAk6SEEEyacH9etQXKUov4JRRuM1Y681VsTq7jYgrRw06cbP6Io7kPsKx+tLFpH/HXZSZ2YEQ==" crossorigin="anonymous"></script>

    <!-- quadtree lib and script -->
    <script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js/quadtree.min.js"></script>
    <script>

        /* ============================= */
        /* patch retrieve function START */
        /* see https://github.com/timohausmann/quadtree-js/issues/17 */
        /* ============================= */

        Quadtree.prototype.retrieve = function (pRect) {

            var indexes = this.getIndex(pRect),
                objects = this.objects;

            //modification: 
            //collect nodes that match the query
            var nodes = [];
            if (this.objects.length) nodes.push(this);


            //if we have subnodes, retrieve their objects
            if (this.nodes.length) {
                for (var i = 0; i < indexes.length; i++) {

                    //modification: collect objects and nodes
                    const retrieved = this.nodes[indexes[i]].retrieve(pRect);
                    objects = objects.concat(retrieved.objects);
                    nodes = nodes.concat(retrieved.nodes);
                }
            }

            //remove duplicate objects
            objects = objects.filter(function (item, index) {
                return objects.indexOf(item) >= index;
            });

            //modification: return objects and nodes
            return {
                objects: objects,
                nodes: nodes
            }
        };

        /* ============================= */
        /* patch retrieve function END */
        /* ============================= */



        (function (w, M) {

            w.requestAnimFrame = (function () {
                return w.requestAnimationFrame ||
                    w.webkitRequestAnimationFrame ||
                    w.mozRequestAnimationFrame ||
                    w.oRequestAnimationFrame ||
                    w.msRequestAnimationFrame ||
                    function (callback) {
                        w.setTimeout(callback, 1000 / 60);
                    };
            })();

            /*
             * the main Quadtree
             */
            var myTree = new Quadtree({
                x: 0,
                y: 0,
                width: 640,
                height: 480
            }, 4);

            /*
             * our objects will be stored here
             */
            var myObjects = [];

            for (var i = 0; i < 50; i++) { 
                var rect = {
                    x: randMinMax(0, myTree.bounds.width - 32),
                    y: randMinMax(0, myTree.bounds.height - 32),
                    width: randMinMax(4, 32, true),
                    height: randMinMax(4, 32, true),
                    check: false
                };

                //store object in our array
                myObjects.push(rect);

                //insert object in our quadtree
                myTree.insert(rect);
            };


            /*
             * our "hero", aka the mouse cursor.
             * He is not in the quadtree, we only use this object to retrieve objects from a certain area
             */
            var myCursor = {
                x: 0,
                y: 0,
                width: 28,
                height: 28
            };

            var isMouseover = false;

            var ctx = document.getElementById('canvas').getContext('2d');

            var cnt_total = document.querySelector('#cnt_total'),
                cnt_cand = document.querySelector('#cnt_cand'),
                cnt_perc = document.querySelector('#cnt_perc');


            /*
             * position hero at mouse
             */
            var handleMousemove = function (e) {

                isMouseover = true;

                if (!e.offsetX) {
                    e.offsetX = e.layerX - e.target.offsetLeft;
                    e.offsetY = e.layerY - e.target.offsetTop;
                }

                myCursor.x = e.offsetX - (myCursor.width / 2);
                myCursor.y = e.offsetY - (myCursor.height / 2);
            };


            /*
             * hide hero
             */
            var handleMouseout = function (e) {

                isMouseover = false;
            };


            /*
             * draw Quadtree nodes
             */
            var drawQuadtree = function (node) {

                var bounds = node.bounds;

                //no subnodes? draw the current node
                if (node.nodes.length === 0) {
                    if (node.check) {
                        ctx.strokeStyle = 'rgba(255,255,255,1)';
                    } else {
                        ctx.strokeStyle = 'rgba(255,0,0,0.5)';
                    }
                    ctx.strokeRect(bounds.x, bounds.y, bounds.width, bounds.height);

                    //has subnodes? drawQuadtree them!
                } else {
                    for (var i = 0; i < node.nodes.length; i = i + 1) {
                        drawQuadtree(node.nodes[i]);
                    }
                }
            };

            /*
             * draw all objects
             */
            var drawObjects = function () {

                var obj;

                for (var i = 0; i < myObjects.length; i = i + 1) {

                    obj = myObjects[i];

                    if (obj.check) {
                        ctx.fillStyle = 'rgba(48,255,48,0.5)';
                        ctx.fillRect(obj.x, obj.y, obj.width, obj.height);
                    } else {
                        ctx.strokeStyle = 'rgba(255,255,255,0.5)';
                        ctx.strokeRect(obj.x, obj.y, obj.width, obj.height);
                    }


                }
            };

            /*
             * our main loop
             */
            var loop = function () {

                var candidates = [];

                ctx.clearRect(0, 0, 640, 480);

                //reset myObjects check flag
                for (var i = 0; i < myObjects.length; i = i + 1) {
                    myObjects[i].check = false;
                }

                //reset nodes check flag
                resetFlag(myTree);
                function resetFlag(node) {
                    node.check = false;
                    for (let i = 0; i < node.nodes.length; i++) {
                        resetFlag(node.nodes[i]);
                    }
                }


                if (isMouseover) {

                    ctx.fillStyle = 'rgba(255,255,255,0.5)';
                    ctx.fillRect(myCursor.x, myCursor.y, myCursor.width, myCursor.height);

                    //retrieve all objects in the bounds of the hero 
                    candidates = myTree.retrieve(myCursor);

                    //flag retrieved objects
                    for (i = 0; i < candidates.objects.length; i = i + 1) {
                        candidates.objects[i].check = true;
                    }

                    //flag retrieved nodes
                    for (i = 0; i < candidates.nodes.length; i = i + 1) {
                        candidates.nodes[i].check = true;
                    }
                }

                drawQuadtree(myTree);

                drawObjects();

                requestAnimFrame(loop);
            };

            //init first loop
            loop();

            //set eventListener for mousemove
            document.getElementById('canvas').addEventListener('mousemove', handleMousemove);
            document.getElementById('canvas').addEventListener('mouseout', handleMouseout);


            /**
             * return a random number within given boundaries.
             *
             * @param {number} min		the lowest possible number
             * @param {number} max		the highest possible number
             * @param {boolean} round	if true, return integer
             * @return {number} 		a random number
             */
            function randMinMax(min, max, round) {
                var val = min + (Math.random() * (max - min));

                if (round) val = Math.round(val);

                return val;
            };

        })(window, Math);
    </script>
</body>

</html>